package main.adt.queue;

import java.util.Arrays;

/**
 * Created by july on 2015/12/24.
 *
 * 队列的顺序存储---循环队列
 * 为了解决顺序队列的假满问题，应该将已删除的数据所占用的空间重新利用起来，当后面满了，那就再从头开始，也就
 * 是头尾相接的循环，我们把队列的这种头尾相接的顺序存储结构称为循环队列。但此时会引入一个新的问题，就是当
 * rear等于front时为队满和队空的判定条件一样，无法区分了，所以在循环队列中，我们通常保留一个元素空间，也
 * 就是说假如如果队列的容量为5，那么放入4个元素之后我们就说队列已满，无法再装入数据了。
 *
 *
 * 常用操作：
 * 1、初始化建立一个空队列
 * 2、返回队列的长度，返回队列中数据元素个数。
 * 3、加入元素(入队):向队列的rear端插入一个数据元素，队列长度+1
 * 4、删除元素(出队)：从队列的front端删除一个数据元素，队列长度-1，该方法通常返回被删除的数据元素
 * 5、访问队列的前端元素：返回队列的front端的数据元素，但不删除。
 * 6、判断是否为空队列，若为空返回true，不为空返回false。
 * 7、清空队列
 */
public class LoopQueue<E> {

    private static final int DEFAULT_CAPACITY = 5;  //默认初始容量

    private int capacity;                           //容量
    private int rear = 0;                           //队头下标
    private int front = 0;                          //队尾下标
    private Object[] data;                          //数据

    public LoopQueue(){
        this(DEFAULT_CAPACITY);
    }

    public LoopQueue(int capacity){
        if(capacity <= 0){
            throw new IllegalArgumentException("初始集合时capacity参数值不能小于0");
        }
        this.data = new Object[capacity];
        this.capacity = capacity;
    }

    /**
     * 入队
     * 该操作改进了rear的计算方式，所以不会出现假满
     * @param element
     */
    public void add(E element){
        checkCapacity();
        data[rear] = element;
        rear = (rear + 1) % capacity;
    }

    /**
     * 出队
     * 该操作不会出现假满问题
     * @return
     */
    @SuppressWarnings("unchecked")
    public E remove(){
        checkSize();
        E oldData = (E) data[front];
        data[front] = null;
        front = (front + 1) % capacity;
        return oldData;
    }

    /**
     * 访问队头元素
     * @return
     */
    @SuppressWarnings("unchecked")
    public E get(){
        checkSize();
        return (E) data[front];
    }

    /**
     * 判断是否为空队列
     * @return
     */
    public boolean isEmpty(){
        return rear == front;
    }

    /**
     * 返回队列的长度
     *  当rear>front时长度就是rear-front
     *  当rear<front时长度分为两段，第一段front到capacity，第二段0到rear
     *  通用公式就是(rear - front + capacity) % capacity
     * @return
     */
    public int size(){
        return (rear - front + capacity) % capacity;
    }

    /**
     * 清空队列
     */
    public void clear(){
        Arrays.fill(data, null);
        front = rear = 0;
    }

    /**
     *  复写toString方法，便于查看集合中的数据
     *
     */
    @Override
    public String toString(){
        if(front == rear){
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        Object temp;
        if(front < rear){
            for(int i = front;i < rear;i++){
                temp = data[i];
                if(temp != null){
                    sb.append(temp.toString()).append(',');
                }else{
                    sb.append("Null").append(',');
                }
            }
            int len = sb.length();
            sb.delete(len-1,len).append("]");
            return sb.toString();
        }
        for(int i = front;i<capacity;i++){
            temp = data[i];
            if(temp != null){
                sb.append(temp.toString()).append(',');
            }else{
                sb.append("Null").append(',');
            }
        }
        for(int i = 0;i<rear;i++){
            temp = data[i];
            if(temp != null){
                sb.append(temp.toString()).append(',');
            }else{
                sb.append("Null").append(',');
            }
        }
        int len = sb.length();
        sb.delete(len-1,len).append("]");
        return sb.toString();
    }

    /**
     * 判断队列是否能继续加入元素
     * 判断队满的条件分为：
     *      当rear>front时，队满的条件是rear指向capacity-1，如容量为5，那rear=4时，就算已满因为
     *          （4+1）% 5 == 0.
     *      当rear<front时，队满的条件是rear + 1 = front。如果容量为5，当rear=1,front=2,就算已满
     *          (1+1)%5 == 2.
     * 通用判断公式就是front == ((rear + 1) % capacity)
     *
     */
    private void checkCapacity(){
        if(front == ((rear + 1) % capacity)){
            throw new IndexOutOfBoundsException("当前队列已满,无法继续添加元素");
        }
    }

    /**
     * 判断队列是否能访问队头元素
     */
    private void checkSize(){
        if(isEmpty()){
            throw new NullPointerException("当前队列为空，无法访问队头元素");
        }
    }

}
